package com.gitee.ywj1352.leecode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author wenjie.yang on 2019/9/25.
 */
public class Leecode01 {


    /**
     * 输入: [[1,3],[2,6],[8,10],[15,18]]
     * 输出: [[1,6],[8,10],[15,18]]
     * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals == null || intervals.length == 0)
            return res.toArray(new int[0][]);
        //先排序
        Arrays.sort(intervals, Comparator.comparingInt(s -> s[0]));
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            //再吞并
            while (i < intervals.length - 1 && right >= intervals[i + 1][0]) {
                right = Math.max(right, intervals[i + 1][1]);
                i++;
            }
            res.add(new int[]{left, right});
        }
        return res.toArray(new int[0][]);
    }

    @Test
    public void testMerge() {
        int[][] merge = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] merge1 = merge(merge);
        for (int[] arr : merge1) {
            System.out.println(arr[0] + ":" + arr[1]);
        }
    }


    /**
     * 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
     * 输出: [[1,2],[3,10],[12,16]]
     * 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
     *
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            res.add(intervals[i]);
        }
        res.add(newInterval);
        intervals = res.toArray(new int[0][]);
        Arrays.sort(intervals, Comparator.comparingInt(s -> s[0]));
        res.clear();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            //再吞并
            while (i < intervals.length - 1 && right >= intervals[i + 1][0]) {
                right = Math.max(right, intervals[i + 1][1]);
                i++;
            }
            res.add(new int[]{left, right});
        }
        return res.toArray(new int[0][]);
    }

    @Test
    public void testInsert() {
        /**
         * [[1,5]]
         * [5,7]
         */
        int[][] merge = {{1, 5}};
        int[][] merge1 = insert(merge, new int[]{5, 7});
        for (int[] arr : merge1) {
            System.out.println(arr[0] + ":" + arr[1]);
        }
    }

}
